package greed;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/*

4 10
0 1 1
1 0 1
1 2 2
2 1 2
2 3 100
3 2 100
3 0 1
0 3 1
1 3 3
3 1 3



 */
public class MinSpaningTree2 {
    
    static InOut4 io = new InOut4();
    static final int MAX_WEIGHT = 0x0000ffff;
    int vertexCount;
    int edgeCount;
    int[][] graph;
    
    

    private MinSpaningTree2(int vertexCount, int edgeCount, int[][] graph) {
        super();
        this.vertexCount = vertexCount;
        this.edgeCount = edgeCount;
        this.graph = graph;
    }

    /*
    
    prim算法是把顶点分成两堆，一堆是访问过的顶点，另一堆是未访问过的顶点。
    找访问过的顶点到未访问的顶点最短的一条边
    
    和dijkstra算法的处理基本一样，只是distance数组换成了lowcost数组，
    每轮选出的是离访问过的顶点最近的未访问顶点，而不是离源点最近的未访问点
    
     */
    
    public void prim() {
        int[] lowcost = new int[vertexCount];
        int[] previous = new int[vertexCount];
        boolean[] visited = new boolean[vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            lowcost[i] = graph[0][i];
            if (graph[0][i] == MAX_WEIGHT) {
                previous[i] = -1;
            } else {
                previous[i] = 0;
            }
        }
        previous[0] = -1;
        lowcost[0] = 0;
        visited[0] = true;
        for (int i = 0; i < vertexCount; i++) {
            int t = -1;
            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && (t == -1 || lowcost[j] < lowcost[t])) {
                    t = j;
                }
            }
            io.out.println(t);
            io.out.println(Arrays.toString(lowcost));
            io.out.println(Arrays.toString(previous));
            io.out.println(Arrays.toString(visited));
            if (t == -1) {
                break;
            }
            visited[t] = true;
            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && graph[t][j] < MAX_WEIGHT) {
                    lowcost[j] = graph[t][j];
                    previous[j] = t;
                }
            }
        }
        io.out.println(Arrays.toString(lowcost));
        io.out.println(Arrays.toString(previous));
        io.out.println(Arrays.toString(visited));
        for (int i = 1; i < vertexCount; i++) {
            io.out.println(i + "-" + previous[i]);
        }
    }
    
    public static void main(String[] args) {
        int vertexCount = io.nextInt();
        int edgeCount = io.nextInt();
        int[][] graph = new int[vertexCount][vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (i != j) {
                    graph[i][j] = MAX_WEIGHT;
                }
            }
        }
        for (int i = 0; i < edgeCount; i++) {
            graph[io.nextInt()][io.nextInt()] = io.nextInt();
        }
        MinSpaningTree2 m = new MinSpaningTree2(vertexCount, edgeCount, graph);
        m.prim();
        io.out.flush();

    }
    
}


class InOut4 {
    BufferedReader br;
    StringTokenizer tok;
    PrintWriter out;
    InOut4() {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }
    public boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                // TODO Auto-generated catch block
                return false;
            }
        }
        return true;
    }
    public String next() {
        if (hasNext()) {
            return tok.nextToken();
        }
        return null;
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    
}
